problem transformation - NISHIO Hirokazu's Scrapbox (Auto-translated from Japanese)

problem transformation

https://gyazo.com/25b6533da9d20f64c553e9091a64d635

Some abstract solution A can solve some concrete problem X.

This is self-evident if you know A

But sometimes a surprising problem Y can be solved with A

There exists a certain problem transformation B that maps some problems to others.

maximum flow minimum cut theorem and

This maps Y, which at first glance is not included in A, to Y', which is included in A.

What else could be in the problem conversion?

Solving a problem represented by a vector by transforming it into a complex number vector complex transformation.

Exchange of value range and definition range

Consider a set of numbers as a sequence of 0/1's and use [Fennic tree

coordinate compression to set the value in the computable range

DP a huge integer as a sequence of digits Digit DP.

Attribute Project Selection Problem to [least-cost current

Consider a number series problem as a [formal power series

dual linear programming problem

---

This page is auto-translated from /nishio/問題変換. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.